package letcode.problem.dynamicProgra;

/**
 * https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming
 */
public class LongestPalindromicSubstring {
    /**
     * 给你一个字符串 s，找到 s 中最长的回文
     * 子串
     * 。
     * <p>
     * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
     * aba
     * aabb
     */
    public static String longestPalindrome(String s) {

        int m = s.length();
        boolean[][] f = new boolean[s.length()][s.length()];
        for (int i = 0; i < m; i++) {
            f[i][i] = true;
        }
        int startIndex = 0;
        int maxLen = 1;

        char[] charArray = s.toCharArray();
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i] != charArray[j]) {
                    f[i][j] = false;
                }else {
                    if (j - i < 3) {
                        f[i][j] = true;
                    }else {
                        f[i][j] = f[i + 1][j - 1];
                    }
                }
                if (f[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    startIndex = i;
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLen);
    }

    public static String lps(String s) {
        char[] charArray = s.toCharArray();
        int m = charArray.length;
        boolean[][] dp = new boolean[m][m];
        for (int i = 0; i < m; i++) {
            dp[i][i] = true;
        }
        int startIndex = 0;
        int maxLen = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < i; j++) {
                if (charArray[i]!=charArray[j]){
                    dp[j][i] = false;
                }else {
                    if (i - j < 3) {
                        dp[j][i] = false;
                    }else {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                }
                if (dp[j][i]&&i-j+1>maxLen){
                    maxLen = i - j + 1;
                    startIndex = i;
                }
            }
        }
        return s.substring(startIndex, startIndex + maxLen);
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("aaaaaaaaaaa"));
    }
}
